package com.fyl.leetcode.doublePointer;

import java.util.List;

/**
 * @author:fyl
 * @date 2021/4/25 13:39
 * @Modified By:
 * @Modified Date:
 * @Description: 题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。
 * Input:
 * s = "abpcplea", d = ["ale","apple","monkey","plea"]
 * <p>
 * Output:
 * "apple"
 */
public class LongestWord {
    public String findLongestWord(String s, List<String> dictionary) {
        String longestWord = "";
        for (String target : dictionary) {
            int lonLen = longestWord.length();
            int tarLength = target.length();
            if (tarLength < lonLen || (tarLength==lonLen && longestWord.compareTo(target) < 0)) {
                continue;
            }

            if (isSubStr(s, target)) {
                longestWord = target;
            }
        }

        return longestWord;
    }

    /**
     * 判断目标单词是否在字符串中
     * i指针遍历字符串
     * j指针遍历目标单词
     * 当两指针指向的字母相同时 j++
     * 最后判断目标单词的字母是否全在字符串中
     * 即：j指针的大小是否为target单词的长度
     *
     * @param s      字符串
     * @param target 目标单词
     * @return 匹配是否成功
     */
    public boolean isSubStr(String s, String target) {
        int i = 0;
        int j = 0;
        while (i < s.length() && j < target.length()) {
            if (s.charAt(i) == target.charAt(j)) {
                j++;
            }
            i++;
        }
        return j == target.length();
    }
}
